//用遗传算法解决旅行商问题
//connect all Path in an arbitary path
//pick two points along the path at random
//split the path at these points, producing three pieces
//try all six possible ways to connect the three pieces
//keep the best one, and reconnect the path accordingly
//iterate the steps until no improvement is observed for a while
#include <stdio.h>
#include <stdlib.h>
#define CITY 20
#define MAXDIS 300


int Path[CITY], BestChild[CITY];

int Map[CITY][CITY];

/* randomly generate the begin path */
void GiveRandomPath (void)
{
    int tmp, rand_i, rand_j;
    for(int i = 0;i < CITY;i++)
        Path[i] = i;
    for(int i = 0;i < CITY;i++)
    {
        rand_i = rand() % CITY;
        rand_j = rand() % CITY;
        tmp = Path[rand_i];
        Path[rand_i] = Path[rand_j];
        Path[rand_j] = tmp;
    }
}

void GiveRandomMap (void)
{
    for(int i = 0;i < CITY;i++){
        for(int j = i+1;j < CITY;j++)
            Map[j][i] = rand() % MAXDIS + 1, Map[i][j] = Map[j][i];
        Map[i][i] = 0;
    }
}

int GivePathDistance (int * path)
{
    int dis = 0;
    for(int i = 0;i < CITY-1;i++)
        dis += Map[path[i]][path[i+1]];
    dis += Map[path[CITY-1]][path[0]];
    return dis;
}

void PrintPath (int * path)
{
    printf("\n------------------------------------------------------------\nPath: \n");
    for(int i = 0;i < CITY;i++)
        printf("%d\t",path[i]);
    printf("\n------------------------------------------------------------\n");
}

int GiveChild (void)
{
    /* randomly generate cut_1, cut_2, ensuring they are not equal */
    int cut_1 = rand()%(CITY-1), cut_2 = (cut_1 + rand()%(CITY-2) + 1)%(CITY-1);
    int R_cut_1 = (cut_1 < cut_2)? cut_1: cut_2;
    int R_cut_2 = (cut_1 < cut_2)? cut_2: cut_1;
    int seg1[R_cut_1+1], seg2[R_cut_2 - R_cut_1], seg3[CITY-R_cut_2-1];
    int len1 = R_cut_1+1, len2 = R_cut_2 - R_cut_1, len3 = CITY-R_cut_2-1;
    for(int i = 0;i < len1;i++)
        seg1[i] = Path[i];
    for(int i = 0;i < len2;i++)
        seg2[i] = Path[i+R_cut_1+1];
    for(int i = 0;i < len3;i++)
        seg3[i] = Path[i+R_cut_2+1];

    int CombineSeg (int * a, int * b, int * c, int lena, int lenb, int lenc, int * tmp_path);
    int score[6], tmp_path[6][CITY];
    score[0] = CombineSeg(seg1, seg2, seg3, len1, len2, len3, tmp_path[0]);
    score[1] = CombineSeg(seg1, seg3, seg2, len1, len3, len2, tmp_path[1]);
    score[2] = CombineSeg(seg2, seg1, seg3, len2, len1, len3, tmp_path[2]);
    score[3] = CombineSeg(seg2, seg3, seg1, len2, len3, len1, tmp_path[3]);
    score[4] = CombineSeg(seg3, seg1, seg2, len3, len1, len2, tmp_path[4]);
    score[5] = CombineSeg(seg3, seg2, seg1, len3, len2, len1, tmp_path[5]);
    int MinScore = GivePathDistance(Path);
    int MinChoice = -1;
    for(int i = 0;i < 6;i++)
    {
        if(score[i] <= MinScore)
            MinScore = score[i],MinChoice = i;
    }
    if(MinChoice == -1)
        for(int i = 0;i < CITY;i++)
            BestChild[i] = Path[i];
    else
        for(int i = 0;i < CITY;i++)
            BestChild[i] = tmp_path[MinChoice][i];
    return MinScore;
}

int CombineSeg (int * a, int * b, int * c, int lena, int lenb, int lenc, int * tmp_path)
{
    for(int i = 0;i < lena;i++)
        tmp_path[i] = a[i];
    for(int i = lena; i < lena + lenb;i++)
        tmp_path[i] = b[i-lena];
    for(int i = lena + lenb; i < lena + lenb + lenc;i++)
        tmp_path[i] = c[i-lena-lenb];
    return GivePathDistance(tmp_path);
}

void LetChildGrow (void)
{
    for(int i = 0;i < CITY;i++)
        Path[i] = BestChild[i];
}

int GA (void)
{
    int MinScore, CurScore, MinStep = 0, generations = 0;
    while(1){
        CurScore = GiveChild();
        generations++;
        if(MinScore==CurScore)
            MinStep++;
        else
            MinStep = 0;
        MinScore = CurScore;
        LetChildGrow();
        if(MinStep > 100)
            break;
    }
    return generations;
}

int main (void)
{
    GiveRandomPath();
    GiveRandomMap();
    PrintPath(Path);
    printf("Initial Dis: %d\n",GivePathDistance(Path));
    printf("Generations: %d\n",GA());
    PrintPath(Path);
    printf("Now Dis: %d\n",GivePathDistance(Path));
}